package 动态规划;

public class Solution279完全平方数 {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for(int i=1;i<=n;i++){
            /*最坏情况是都是1组成的*/
            dp[i]=i;
            for(int j=1;i-j*j>=0;j++){
                /* dp[0]=0;
                 * dp[1]=1;
                 * dp[2]=min(dp[1]+1,dp[2)=2);
                 * dp[3]=min(dp[3-1*1]+1,dp[3])=3;
                 * dp[4]=min(dp[4-2*2])+1,dp[4])=1;
                 * dp[5]=min(dp[5-2*2]+1,dp[5])=dp[1]+1=2;
                 */
                dp[i]= Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}
